package com.fang.algorithm.zuo.sort;

import java.util.Arrays;

/**
 * @author lingxiao.fang
 * @Desc 归并排序
 * @createTime 2025/2/10 13:36
 */
public class Test06_MergeSort {

    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
//        mergeSort1(arr);
//        mergeSort2(arr);
        System.out.println(Arrays.toString(arr));
        int[] nums1 = {1, 2};
        int[] nums2 = {3};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    /**
     * 归并排序-递归方法实现
     */
    private static void mergeSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        mergeSortProcess(arr, 0, arr.length - 1);
    }

    private static void mergeSortProcess(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSortProcess(arr, left, mid);
        mergeSortProcess(arr, mid + 1, right);
        mergeArr(arr, left, mid, right);
    }

    private static void mergeArr(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int index = 0;
        int p1 = left;
        int p2 = mid + 1;
        // p1 p2指针未越界情况下，谁的值小谁赋值给help[index]，然后index++，p1/p2++
        while (p1 <= mid && p2 <= right) {
            if (arr[p1] <= arr[p2]) {
                help[index] = arr[p1];
                p1++;
            } else {
                help[index] = arr[p2];
                p2++;
            }
            index++;
        }
        // p1或者p2越界，将剩余的值赋值给help[index]
        while(p1 <= mid) {
            help[index] = arr[p1];
            index++;
            p1++;
        }
        while (p2 <= right) {
            help[index] = arr[p2];
            index++;
            p2++;
        }
        // 将help数组的值赋值给arr
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
    }

    /**
     * 归并排序-非递归方法实现
     */
    private static void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

    }

    private static int arrSmallSum(int[] arr) {
        // 数组小和
        if (arr == null || arr.length < 2) {
            return -1;
        }
        return 0;
    }


    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length == 0 && nums2.length == 0) {
            return -1;
        }
        // 合并
        int length = nums1.length + nums2.length;
        int[] mergeArr = new int[length];
        for (int i = 0; i < nums1.length; i++) {
            mergeArr[i] = nums1[i];
        }
        for (int i = 0; i < nums2.length; i++) {
            mergeArr[nums1.length + i] = nums2[i];
        }
        // 排序
        mergeSortProcess2(mergeArr, 0, mergeArr.length - 1);
        // 计算中位数
        double ans;
        if (length % 2 == 0) {
            int less = (1 + length - 1) >> 1;
            int more = (1 + length + 1) >> 1;
            ans = ((double) mergeArr[less - 1] + mergeArr[more - 1]) / 2;
        } else {
            int mid = (1 + length) >> 1;
            ans = (double) mergeArr[mid - 1];
        }
        return ans;
    }

    private static void mergeSortProcess2(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = (L + R) / 2;
        mergeSortProcess2(arr, L, mid);
        mergeSortProcess2(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }

    private static void merge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int index = 0;
        int p1 = L;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= R) {
            if (arr[p1] <= arr[p2]) {
                help[index] = arr[p1];
                p1++;
            } else {
                help[index] = arr[p2];
                p2++;
            }
            index++;
        }
        while (p1 <= mid) {
            help[index] = arr[p1];
            p1++;
            index++;
        }
        while (p2 <= R) {
            help[index] = arr[p2];
            p2++;
            index++;
        }
        for (int i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }
}
